/**
 * @file JgLockFreeQueue.hpp
 * @author Wangzhengqiao (me@zhengqiao.wang)
 * @brief 无锁队列
 * @version 0.1
 * @date 2021-09-24
 * 
 * 该无锁队列线程安全，有ABA风险。
 * 讲解时：
 * 介绍什么是无锁队列
 * 什么是CAS
 * 什么是自旋锁
 * 无锁队列实质是硬件锁实现的队列
 * 代码解释
 */

#ifndef JGLOCK_FREE_QUEUE_HPP
#define JGLOCK_FREE_QUEUE_HPP

#include <atomic>
#include <assert.h>
#include <thread>

template <typename T>
class JgLockFreeQueue
{
public:
    JgLockFreeQueue()
    {
        Node *node = new Node(Empty);
        m_head.store(node);
        m_tail.store(node); // 初始化时，head=tail=空
        m_isLockFree = node->val.is_lock_free();
    }
    ~JgLockFreeQueue()
    {
        T val = Empty;
        while (tryPop(val))
        {
        }
        Node *node = m_head.load();
        if (node != nullptr)
            delete node;
    }

public:
    bool isLockFree()
    {
        return m_isLockFree.load();
    }

    int getCount()
    {
        return m_count.load();
    }

    /**
     * @brief 队列添加数据
     * 对tail成功CAS为nullptr 表示当前线程获取tail自旋锁成功，并设置tail的next节点为push的元素，解锁tail，即将tail进行CAS为tail->next;
     * 
     * @param val 
     * @return true 
     * @return false 
     */
    bool tryPush(T val)
    {
        Node *t = nullptr;
        Node *node = new Node(val);

        while (1)
        {
            // t==NULL，表示tail锁被抢
            if (nullptr == t)
            {
                t = m_tail.load();
                continue;
            }
            //尝试加tail锁
            if (!m_tail.compare_exchange_weak(t, nullptr))
            {
                continue;
            }
            break;
        }

        // 到此处表明已抢到
        t->next.store(node);
        ++m_count;
        Node *expected = nullptr;
        // 释放tail锁
        bool flag = m_tail.compare_exchange_weak(expected, t->next);
        assert(flag);
        return flag;
    }

    /**
     * @brief 
     * 对head成功CAS为NULL 表示当前线程获取head自旋锁成功，并需要判断当前数组是否为空，如果为空，则解锁并返回为false；否则成功，则pop出数据head->next->val，最后解锁，即将head进行CAS为head->next；
     * 
     * @param val 
     * @return true 
     * @return false 
     */
    bool tryPop(T &val)
    {
        Node *h = nullptr;
        Node *h_next = nullptr;

        while (1)
        {
            //h==NULL，表示head锁被抢
            if (nullptr == h)
            {
                h = m_head.load();
                continue;
            }
            //尝试加head锁
            if (!m_head.compare_exchange_weak(h, nullptr))
            {
                continue;
            }
            h_next = h->next.load();
            // h->next != NULL 且 count == 0
            // 此时在push函数中数据以及count计数器没有来得及更新，因此进行自旋
            if (nullptr != h_next)
            {
                while (m_count.load() == 0)
                {
                    std::this_thread::yield(); // 让渡时间片
                }
            }
            break;
        }
        Node *expected = nullptr;
        Node *desired = h;
        // 当h_next==NULL时
        // 表示当前链表为空
        if (nullptr != h_next)
        {
            val = h_next->val;
            delete h;
            desired = h_next;
            --m_count;
        }
        //CAS head，释放head锁
        bool flag = m_head.compare_exchange_weak(expected, desired);
        assert(flag);
        return (h_next != nullptr);
    }

private:
    struct Node
    {
        std::atomic<T> val;       ///< 保存的值
        std::atomic<Node *> next; ///< 链表向下指针
        Node(T val) : val(val) {} ///< 初始化
    };
    const T Empty = 0;

    std::atomic<int> m_count{0};   ///< 队列计数器
    std::atomic<Node *> m_head;    ///< 头节点
    std::atomic<Node *> m_tail;    ///< 尾节点
    std::atomic_bool m_isLockFree; ///< lockfree标志位
};

#endif